This disclosure relates generally to methods and systems for production/manufacturing planning and scheduling. More specifically the disclosure relates to the planning of operations for manufacturing or production tasks by solving multiple interacting state-space search problems.
Production/Manufacturing plants or other environments conventionally require the planning and scheduling of a series of jobs. Because execution of plans requires the use of physical plant resources, planning for later jobs must take into account the resource commitments in plans already released for production. For example, if part 1 is scheduled to use machine 2 for 15 seconds starting at 4:00:00 pm, the plan for part 2 cannot use machine 2 from 4:00:00 to 4:00:15 pm. While production planning and scheduling may be simple for systems that manufacture many identical jobs in an assembly-line fashion, or factories that produce a very small number of custom jobs over a long period of time, it can be extremely difficult in situations involving high-speed custom made-to-order manufacturing, in which different objects may require different processing and the production plan for an object must be created very quickly.
A typical manufacturing plant may be represented as a network of transports linking multiple machines, as shown in FIG. 1. A plant may have anywhere from a few to a several hundred machines and transports. Unfinished blocks of raw material may enter the plant from multiple sources and completed jobs can exit at multiple destinations. In the simplified schematic of FIG. 1, sources 1 and 2 provide materials to Machine 1 and Machine 2, which interface with Machine 3 and Machine 4 as well as Destinations 1 and 2. Transports between sources, machines, and destinations take a known time to convey jobs. Each machine has a limited number of discrete actions it can perform, each of which has a known duration and transforms its input in a known deterministic way.
From a planning perspective, jobs can move through the plant as illustrated in FIG. 2. A job request specifies a desired final configuration, which may be achievable by several different sequences of actions. For example, in FIG. 2 material may be procured from source S1 to be received and processed by machine M1 utilizing either a first or second operation Act1 or Act2. At the completion of either Act1 or Act2, materials may be sent to destination D1, to machine M3, or to machine M2 for further processing. The plant might operate at high speed, with multiple job requests arriving per second, possibly for many hours. Clearly, a fast, automated procedure is necessary to coordinate production, and one that optimizes the throughput of the plant would be advantageous.
The optimal plan for a job depends not only on the job request, but also on the resource commitments present in previously-planned jobs. Most existing approaches to this problem require the enumeration of all possible plans at machine start-up, with retrieval of a suitable plan for each job request and then scheduling of the necessary actions. However, the large number of potential plans in more complex plants makes an on-line planning system desirable. Furthermore, it may not be possible to pre-compute optimal plans because the plan that optimizes plant throughput will depend on the other jobs being processing in the plant at the same time.
The disclosure in U.S. patent application US 2005/0278303 A1 to Ruml et al. is directed to an on-line planning system. In the Ruml et al. application, the plan represents the actions of multiple machines on a single object and the state in each node represents only the state of the object. In contrast with previous work, the machines are likely to be already in operation processing previous jobs during the planning for a new job, and the world consists of many objects being manipulated simultaneously.
In some instances an on-line planning system, as well as other planning systems which do not provide on-line planning, may benefit by considering individual interacting problems of the overall problem as linked problems.